

# 深度优先

""" res = []
def compute(root,path):
    if root:
        path += str(root.val)

        # 递归终止条件
        if not root.left and not root.right:
            res.append(path)
        else:
            path += "->"
            
            # 递归遍历 
            compute(root.left,path)
            compute(root.right,path)
compute(root, "")
return res """




# 广度优先
paths = list()
if not root:
    return paths

node_queue = collections.deque([root])
path_queue = collections.deque([str(root.val)])

while node_queue:
    node = node_queue.popleft()
    path = path_queue.popleft()

    if not node.left and not node.right:
        paths.append(path)
    else:
        if node.left:
            node_queue.append(node.left)
            path_queue.append(path + '->' + str(node.left.val))
        
        if node.right:
            node_queue.append(node.right)
            path_queue.append(path + '->' + str(node.right.val))
return paths
